We study the non-uniform capacitated multi-item lot-sizing (\lotsizing)problem. In this problem, there is a set of demands over a planning horizon of$T$ time periods and all demands must be satisfied on time. We can place anorder at the beginning of each period $s$, incurring an ordering cost $K_s$.The total quantity of all products ordered at time $s$ can not exceed a givencapacity $C_s$. On the other hand, carrying inventory from time to time incursinventory holding cost. The goal of the problem is to find a feasible solutionthat minimizes the sum of ordering and holding costs. Levi et al.\ (Levi, Lodi and Sviridenko, Mathmatics of Operations Research33(2), 2008) gave a 2-approximation for the problem when the capacities $C_s$are the same. In this paper, we extend their result to the case of non-uniformcapacities. That is, we give a constant approximation algorithm for thecapacitated multi-item lot-sizing problem with general capacities. The constant approximation is achieved by adding an exponentially large setof new covering inequalities to the natural facility-location type linearprogramming relaxation for the problem. Along the way of our algorithm, wereduce the \lotsizing problem to two generalizations of the classic knapsackcovering problem. We give LP-based constant approximation algorithms for bothgeneralizations, via the iterative rounding technique.
展开▼
机译：我们研究了不均匀的容量化多项目批量确定（\ lotsizing）问题。在此问题中，在$ T $时间段的计划范围内存在一组需求，并且必须按时满足所有需求。我们可以在每个期初$ s $下订单，导致订购成本$ K_s $。在时间$ s $下订购的所有产品的总数量不能超过给定的容量$ C_s $。另一方面，不定期结转存货会产生存货成本。该问题的目的是找到一种可行的解决方案，以最大程度地减少订购和保持成本的总和。当容量$ C_s $相同时，Levi等人（Levi等人，Lodi和Sviridenko，《运筹学研究》 33（2），2008）给出了问题的2个近似值。在本文中，我们将其结果扩展到容量不均匀的情况。也就是说，对于具有一般能力的多项目批量问题，我们给出了一个常数近似算法。通过向自然设施-位置类型的线性规划松弛问题中添加指数级的一组新的覆盖不等式，可以实现常数近似。沿着我们的算法，将\ lotsizing问题归结为经典背包问题的两个推广。通过迭代舍入技术，我们为两种泛化提供了基于LP的常数逼近算法。
展开▼
